package gsolver;

import org.apache.commons.math.genetics.CrossoverPolicy;
import org.apache.commons.math.genetics.Chromosome;
import org.apache.commons.math.genetics.ChromosomePair;
import org.apache.commons.math.genetics.Population;

import gsolver.GChromosome;
import gsolver.GFirstFitModifie;

import java.util.Random;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collection;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * Algorithme de croisement. Implémente l'algorithme BPRX
 * décrit dans "A Hybrid Grouping Genetic Algorithm for
 * Bin Packing", par Emanuel Falkenauer.
 */
public class GCrossoverBPRX implements CrossoverPolicy {
    private Random rand;

    public GCrossoverBPRX(Random rand) {
	this.rand = rand;
    }

    /**
     * L'algorithme de croisement BPRX est le suivant:
     * Soient ABCDEF et abcd deux chromosomes, où un gène est un lot.
     * On choisit deux points de croisement aléatoires dans chaque
     * chromosomes, par exemple:
     * A|BCD|EF
     * ab|cd|
     * Dans une première étape, on injecte les lots entre les points
     * de croisement du deuxième chromosome dans le premier chromosome
     * au niveau du premier point de croisement:
     * AcdBCDEF
     * On a maintenant peut-être plusieurs lots contenant les mêmes jobs,
     * on retire alors les anciens lots provoquant le conflit, par exemple
     * C, E et F:
     * AcdBD
     *
     * Il manque maintenant des objets à la solution: pour les réinsérer, on
     * essaie d'abord pour chaque lot, de voir s'il est possible de remplacer
     * au plus trois jobs (pour des raisons de complexité algorithmique) par
     * un ou deux jobs parmis ceux qu'on souhaite réinsérer, en augmentant la
     * la taille contenue dans le lot, et aussi (pour prendre en compte les contraintes
     * particulières de notre problème) en réduisant le coût de stockage minimal
     * du nouveau lot.
     *
     * Celles qui ne sont toujours pas insérées sont insérées avec
     * l'heuristique FFD, qui consiste à prendre les jobs dans l'ordre de leur
     * taille dans l'ordre décroissant, et les ranger dans le premier lot pouvant 
     * les acceuillir. Pour prendre en compte les contraintes particulières de
     * notre problème, on insère un job dans un lot existant seulement si le coût
     * ajouté par l'insertion est inférieur au coût de la création d'un nouveau lot
     * contenant seulement ce job.
     *
     * Même procédé pour le deuxième.
     */
    public ChromosomePair crossover(Chromosome first, Chromosome second) {
	GChromosome fst = (GChromosome)first;
	GChromosome snd = (GChromosome)second;
	int point1_1 = rand.nextInt(fst.getLength());
	int point1_2 = point1_1 + 1 + rand.nextInt(fst.getLength() - 1 - point1_1);
	int point2_1 = rand.nextInt(snd.getLength() - 1);
	int point2_2 = point2_1 + 1 + rand.nextInt(snd.getLength() - 1 - point1_1);
	
	return new ChromosomePair(injecter(fst, point1_1, point1_2, snd, point2_1, point2_2),
				  injecter(snd, point2_1, point2_2, fst, point1_1, point2_2));
    }

    /* dominance Pareto selon deux critère: la taille et le coût de stockage.
       Un job est considéré plus petit s'il est meilleur, càd si son coût est
       plus faible et que sa taille est plus grande, et que l'un des deux l'est
       strictement. */
    private class ComparatorTailleCoutJobs implements Comparator<Integer> {
	public ComparatorTailleCoutJobs() {
	    return;
	}

	public int compare(Integer job1, Integer job2) {
	    double cout1 = GChromosome.getProblem().getJobData()[job1].getHoldingCost();
	    double cout2 = GChromosome.getProblem().getJobData()[job2].getHoldingCost();
	    double taille1 = GChromosome.getProblem().getJobData()[job1].getSize();
	    double taille2 = GChromosome.getProblem().getJobData()[job2].getSize();

	    if (cout1 <= cout2 && taille1 >= taille2 && (cout1 < cout2 || taille1 < taille2)) {
		return -1;
	    } else if (cout2 <= cout1 && taille2 >= taille1 && 
		       (cout2 < cout1 || taille2 < taille1)) {
		return 1;
	    } else {
		return 0;
	    }
	}
    }

    private GChromosome injecter(GChromosome toInject, int point1_1, int point1_2,
				 GChromosome toReceive, int point2_1, int point2_2) {
	/* Au pire, le chromosome recevra tous les lots de toReceive + ceux entre les
	   points de croisement de toInject. */
	ArrayList<Lot> representation = new ArrayList<Lot>(toReceive.getLength() 
							   + point1_2 - point1_1);
	List<Lot> toAdd = toInject.getRepresentation().subList(point1_1 - 1, point1_2 - 1);
	HashSet<Integer> jobsInterdits = union(toAdd);
	
	for (int i = 0; i < point2_1; i++) {
	    if (intersectionEstVide(jobsInterdits, 
				    toReceive.getRepresentation().get(i).getJobs())) {
		representation.add(toReceive.getRepresentation().get(i));
	    }
	}
	for (Lot lot : toAdd) {
	    representation.add(lot);
	}
	for (int i = point2_1; i < toReceive.getLength(); i++) {
	    representation.add(toReceive.getRepresentation().get(i));
	}

	remplacerParDominance(representation, jobsInterdits);

	insererFFD(representation, jobsInterdits);

	return new GChromosome(representation);
    }

    public class TripletJob {
	public Integer first;
	public Integer second;
	public Integer third;

	public TripletJob(Integer first, Integer second, Integer third) {
	    first = first;
	    second = second;
	    third = third;
	}

	public int[] toArray() {
	    if (first == null && second == null && third == null) {
		return null;
	    } else if (second == null && third == null) {
		int[] res = {first};
		return res;
	    } else if (third == null) {
		int[] res = {first, second};
		return res;
	    } else {
		int[] res = {first, second, third};
		return res;
	    }
	}

	public Collection<Integer> toCollection() {
	    return Arrays.asList(first, second, third);
	}
    }

    public class PaireJob {
	public Integer first;
	public Integer second;
	
	public PaireJob(Integer first, Integer second) {
	    first = first;
	    second = second;
	}

	public Integer[] toArray() {
	    if (first == null && second == null) {
		return null;
	    } else if (second == null) {
		Integer[] res = {first};
		return res;
	    } else {
		Integer[] res = {first, second};
		return res;
	    }
	}

	public Collection<Integer> toCollection() {
	    return Arrays.asList(first, second);
	}
    }

    private void remplacerParDominance(ArrayList<Lot> representation, 
				       HashSet<Integer> aInserer) {

	for (int i = 0; i < representation.size(); i++) {
	    Lot lot = representation.get(i);
	    boolean lotRemplace = false;
	    double coutMinimal1 = lot.coutMinimal();
	    double tailleOccupee1 = lot.tailleOccupee();

	    for (TripletJob triplet : triplets(lot.getJobs().toArray(new Integer[1]))) {
		for (PaireJob paire : paires(aInserer.toArray(new Integer[1]))) {
		    Lot nouveauLot = lot.retirerJobs(triplet.toArray())
			                .ajouterJobs(paire.toArray());
		    double coutMinimal2 = nouveauLot.coutMinimal();
		    double tailleOccupee2 = nouveauLot.tailleOccupee();

		    lotRemplace = (coutMinimal1 <= coutMinimal2 && 
				   tailleOccupee1 <= tailleOccupee2);
		    if (lotRemplace) {
			representation.add(i, nouveauLot);
			aInserer.removeAll(paire.toCollection());
			aInserer.retainAll(triplet.toCollection());
			break;
		    }
		}
		if (lotRemplace) {
		    break;
		}
	    }
	}
    }

    private Set<TripletJob> triplets(Integer[] jobs) {
	HashSet<TripletJob> triplets = new HashSet<TripletJob>();

	triplets.add(new TripletJob(null, null, null));
	for (int i = 0; i < jobs.length; i++) {
	    triplets.add(new TripletJob(jobs[i], null, null));
	    for (int j = i; j < jobs.length; j++) {
		triplets.add(new TripletJob(jobs[i], jobs[j], null));
		for (int k = j; k < jobs.length; k++) {
		    triplets.add(new TripletJob(jobs[i], jobs[j], jobs[k]));
		}
	    }
	}
	
	return triplets;
    }

    private Set<PaireJob> paires(Integer[] jobs) {
	HashSet<PaireJob> paires = new HashSet<PaireJob>();

	paires.add(new PaireJob(null, null));
	for (int i = 0; i < jobs.length; i++) {
	    paires.add(new PaireJob(jobs[i], null));
	    for (int j = i; j < jobs.length; j++) {
		paires.add(new PaireJob(jobs[i], jobs[j]));
	    }
	}

	return paires;
    }

    /**
     * Vrai si l'intersection de set1 et set2 est vide
     */
    private boolean intersectionEstVide(Set<Integer> set1, Set<Integer> set2) {
	HashSet<Integer> intersection = new HashSet<Integer>(set1);

	intersection.retainAll(set2);
	
	return intersection.isEmpty();
    }

    private HashSet<Integer> union(List<Lot> lots) {
	HashSet<Integer> resultat = new HashSet<Integer>();

	for (Lot lot : lots) {
	    resultat.addAll(lot.getJobs());
	}

	return resultat;
    }

    private void insererFFD(List<Lot> representation, Set<Integer> jobsARajouter) {
	Integer[] jobs = jobsARajouter.toArray(new Integer[0]);
	Arrays.sort(jobs, new ComparatorTailleCoutJobs());
	GFirstFitModifie.insererFFM(representation, jobs);
    }
}